//1110 Delete Nodes And Return Forest
/*
给定一个整数二叉树和一些整数，求删掉这些整数对应的节点后，剩余的子树

输入是一个整数二叉树和一个一维整数数组，输出一个数组，每个位置存储一个子树（的根
节点）。

Input: to_delete = [3,5], tree =
		1
	   / \
	  2   3
     / \ / \
	4  5 6  7
Output: [
	 1
	/
   2
  /
 4 ,6 ,7]



*/
// 主函数
vector<TreeNode *> delNodes(TreeNode *root, vector<int> &to_delete)
{
	vector<TreeNode *> forest; //
	
	//建立待删除结点的哈希表，方便查找
	unordered_set<int> dict(to_delete.begin(), to_delete.end());
	
	root = helper(root, dict, forest);
	if (root)
	{
		forest.push_back(root);
	}
	return forest;
}
// 辅函数
TreeNode *helper(TreeNode *root, unordered_set<int> &dict, vector<TreeNode *> &forest)
{
	if (!root)
	{
		return root;
	}
	root->left = helper(root->left, dict, forest);
	root->right = helper(root->right, dict, forest);
	if (dict.count(root->val))
	{
		if (root->left)
		{
			forest.push_back(root->left);
		}
		if (root->right)
		{
			forest.push_back(root->right);
		}
		root = NULL;
	}
	return root;
}